package com.feiyue.learning.sort;

import java.util.Arrays;

/**
 * 堆排序
 * @author  feiyue
 * @date  2020/3/29
 */
public class HeapSort {

    public static void main(String[] args) {

        int[] data = new int[]{2, 3, 5, 4, 7, 6, 8, 1};

        System.out.print("排序前: ");
        Arrays.stream(data).forEach(r->System.out.print(r + " "));

        heapSort(data);

        System.out.print("\n排序后: ");
        Arrays.stream(data).forEach(r->System.out.print(r + " "));
    }

    /*
     * 数组从 0 开始, 根和左右节点的关系: n(root) -- 2n+1(左节点) -- 2n+2(右节点)
     */
    private static void heapSort(int[] data) {
        if (data.length <= 1) {
            return;
        }

        // 构建最大堆积树, 仅需要从 半数-->0(半数以下没有左右节点) 依次将大数提升到根节点
        for (int i = (data.length - 1) / 2; i >= 0; i--) {
            sink(data, i, data.length);
        }

        // 依次移除根节点并重新构建最大堆, i 为最大索引
        int i = data.length - 1;
        while(i > 0) {
            exchange(data, 0, i);
            sink(data, 0,  --i);
        }
    }

    private static void sink(int[] data, int i, int length) {

        // 最大堆需要满足所有节点的值大于或等于左右子结点的值, 所有需要递归直至子孙节点都满足(用while而不是if)
        while (i * 2 + 1 <= length - 1) {
            int j = i * 2 + 1;
            if (j < length - 1 && data[j] < data[j+1]) {
                j++;
            }
            if (data[i] < data[j]) {
                exchange(data, i, j);
            }
            i = j;
        }
    }

    private static void exchange(int[] data, int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}
